package com.itheima.algorithm.dynamicprogramming;

/**
 * <h3>旅行商路径 - 动态规划</h3>
 */
public class TravellingSalesmanProblem {

    /*
            0   1   2   3
        0   0   1   2   3
        1   1   0   6   4
        2   2   6   0   5
        3   3   4   5   0

            0                                 1     2   3     4       5       6       7       j 剩余城市集合(代表graph的排序，因为是一个圆圈，所以只需要以0为起点，就包括了所有情况)
            没城市（假设为开始城市，当前为0，正好）   1     2   1|2   3       1|3     2|3     1|2|3
        0
        1
        2
        3
        i   出发城市

        000
        001
        010
        011
        100
        101
        110
        111

     */
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 2, 3},
                {1, 0, 6, 4},
                {2, 6, 0, 5},
                {3, 4, 5, 0}
        };
        System.out.println(tsp(graph));
    }

    static int tsp(int[][] g) {
        int m = g.length; // 城市数目
        int n = 1 << (m - 1);// 剩余城市的组合数 2^(m-1)
        int[][] dp = new int[m][n];
        // 填充第0列
        for (int k = 0; k < m; k++) {
            dp[k][0] = g[k][0];
        }

        // 填充后续列
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                dp[i][j] = Integer.MAX_VALUE / 2;
                if (contains(j, i)) {
                    continue;
                }
                // 填充单元格
                for (int k = 0; k < m; k++) {
                    if (contains(j, k)) {
                        dp[i][j] = Integer.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);
                    }
                }
            }

        }
        return dp[0][n - 1];
    }

    static int exclude(int set, int city) {
        return set ^ (1 << (city - 1));
    }

    static boolean contains(int set, int city) {
        return (set >> (city - 1) & 1) == 1;
    }
}
